
// https://leetcode.cn/problems/generate-parentheses/description/

class Solution
{
    vector<string> res;
    string path;
    int left;
    int right;
    int _n;

public:
    vector<string> generateParenthesis(int n)
    {
        _n = n;
        dfs(0);
        return res;
    }

    void dfs(int len)
    {
        if (len == 2 * _n)
        {
            res.push_back(path);
            return;
        }

        if (left < _n)
        {
            path += "(";
            ++left;
            dfs(len + 1);
            path.pop_back();
            --left;
        }
        if (right < left)
        {
            path += ")";
            ++right;
            dfs(len + 1);
            path.pop_back();
            --right;
        }
    }
};